% BEGIN LICENSE BLOCK
% Version: CMPL 1.1
%
% The contents of this file are subject to the Cisco-style Mozilla Public
% License Version 1.1 (the "License"); you may not use this file except
% in compliance with the License.  You may obtain a copy of the License
% at www.eclipse-clp.org/license.
% 
% Software distributed under the License is distributed on an "AS IS"
% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
% the License for the specific language governing rights and limitations
% under the License. 
% 
% The Original Code is  The ECLiPSe Constraint Logic Programming System. 
% The Initial Developer of the Original Code is  Cisco Systems, Inc. 
% Portions created by the Initial Developer are
% Copyright (C) 2006 Cisco Systems, Inc.  All Rights Reserved.
% 
% Contributor(s): 
% 
% END LICENSE BLOCK

%----------------------------------------------------------------------
\chapter{The Integer Sets Library}
%HEVEA\cutdef[1]{section}
\label{chapfdsets}
\index{library!fd_sets|(}
%----------------------------------------------------------------------


%----------------------------------------------------------------------
%\section{Introduction}
%----------------------------------------------------------------------

The {\em fd_sets} library is a solver for constraints over the domain
of finite sets of integers. Unlike {\em conjunto}, it cannot deal with
sets elements that are not integers. On the other hand, fd_sets is usually
faster for integer sets than conjunto.



\section{Ground Integer Sets}

(Ground) integer sets are simply sorted, duplicate-free lists of integers e.g. 
\begin{verbatim}
        SetOfThree = [1,3,7]
        EmptySet = []
\end{verbatim}
Lists which contain non-integers, are unsorted or contain duplicates,
are not sets in the sense of this library.


%----------------------------------------------------------------------
\section{Set Variables}
%----------------------------------------------------------------------

\subsection{Declaring}
Set variables are variables which can eventually take a ground integer
set as their value.  They are characterized by a lower bound (the set
of elements that are definitely in the set) and an upper bound (the
set of elements that may be in the set).  A set variable can be
declared as follows: 
\begin{verbatim}
        SetVar :: []..[1,2,3,4,5,6,7]
\end{verbatim}
If the lower bound is the empty set (like in this case) this can be written as 
\begin{verbatim}
        SetVar subset [1,2,3,4,5,6,7]
\end{verbatim}
If the lower bound is the empty set and the upper bound is a set of
consecutive integers, one can also declare it like
\begin{verbatim}
        intset(SetVar, 1, 7)
\end{verbatim}
which is equivalent to the above.    

The predicates to declare sets are:
\begin{description}
\item[\biptxtref{?Set :: ++Lwb..++Upb}{::/2!fd_sets}{../bips/lib/fd_sets/NN-2.html}]
         Set is an integer set within the given bounds 
\item[\biptxtref{intset(?Set, +Min, +Max)}{intset/3}{../bips/lib/fd_sets/intset-3.html}]
         Set is a set containing numbers between Min and Max 
\item[\biptxtref{intsets(?Sets, ?N, +Min, +Max)}{intsets/4}{../bips/lib/fd_sets/intsets-4.html}]
         Sets is a list of N sets containing numbers between Min and Max 
\end{description}



\subsection{Printing}

Set variables are by default printed in a particular way, e.g.
\begin{verbatim}
?- X :: [2,3]..[1,2,3,4], write(X).
X{[2, 3] \/ ([] .. [1, 4]) : _308{[2 .. 4]}}
\end{verbatim}
The curly brackets contain
\begin{enumerate}
\item the lower bound of the set
\item the union symbol
\item the set of optional values (that may or may not be in the set)
\item a colon
\item a finite domain indicating the admissible cardinality for the set
\end{enumerate}



\subsection{Domain Access}

\begin{description}
\item[\biptxtref{potential_members(?Set, -List)}{potential_members/2}{../bips/lib/fd_sets/potential_members-2.html}]
         List is the list of elements of whose membership in Set is currently uncertain 
\item[\biptxtref{set_range(?Set, -Lwb, -Upb)}{set_range/3}{../bips/lib/fd_sets/set_range-3.html}]
         Lwb and Upb are the current lower and upper bounds on Set 
\end{description}


%----------------------------------------------------------------------
\section{Constraints}
%----------------------------------------------------------------------

\subsection{Membership}

\begin{description}
\item[\biptxtref{?X in ?Set}{in/2!fd_sets}{../bips/lib/fd_sets/in-2.html}]
         The integer X is member of the integer set Set 
\item[\biptxtref{?X notin ?Set}{notin/2!fd_sets}{../bips/lib/fd_sets/notin-2.html}]
         The integer X is not a member of the integer set Set 
\item[\biptxtref{membership_booleans(?Set, ?BoolArr)}{membership_booleans/2!fd_sets}{../bips/lib/fd_sets/membership_booleans-2.html}]
         BoolArr is an array of booleans describing Set 
\end{description}


\subsection{Cardinality}

\begin{description}
\item[\biptxtref{\#(?Set, ?Card)}{\#/2!fd_sets}{../bips/lib/fd_sets/H-2.html}]
         Card is the cardinality of the integer set Set 
\end{description}


\subsection{Set Relations}

\begin{description}

\item[\biptxtref{difference(?Set1, ?Set2, ?Set3)}{difference/3!fd_sets}{../bips/lib/fd_sets/difference-3.html}]
         Set3 is the difference of the integer sets Set1 and Set2 

\item[\biptxtref{?Set1 disjoint ?Set2}{disjoint/2!fd_sets}{../bips/lib/fd_sets/disjoint-2.html}]
         The integer sets Set1 and Set2 are disjoint 

\item[\biptxtref{?Set1 includes ?Set2}{includes/2!fd_sets}{../bips/lib/fd_sets/includes-2.html}]
         Set1 includes (is a superset) of the integer set Set2 

\item[\biptxtref{intersection(?Set1, ?Set2, ?Set3)}{intersection/3!fd_sets}{../bips/lib/fd_sets/intersection-3.html}]
         Set3 is the intersection of the integer sets Set1 and Set2 

\item[\biptxtref{?Set1 sameset ?Set2}{sameset/2!fd_sets}{../bips/lib/fd_sets/sameset-2.html}]
         The sets Set1 and Set2 are equal 
\item[\biptxtref{?Set1 subset ?Set2}{subset/2!fd_sets}{../bips/lib/fd_sets/subset-2.html}]
         Set1 is a subset of the integer set Set2 
\item[\biptxtref{symdiff(?Set1, ?Set2, ?Set3)}{symdiff/3!fd_sets}{../bips/lib/fd_sets/symdiff-3.html}]
         Set3 is the symmetric difference of the integer sets Set1 and Set2 
\item[\biptxtref{union(?Set1, ?Set2, ?Set3)}{union/3!fd_sets}{../bips/lib/fd_sets/union-3.html}]
         Set3 is the union of the integer sets Set1 and Set2 
\end{description}


\subsection{N-ary Set Relations}

\begin{description}
\item[\biptxtref{all_disjoint(+Sets)}{all_disjoint/1}{../bips/lib/fd_sets/all_disjoint-1.html}]
         Sets is a list of integers sets which are all disjoint 
\item[\biptxtref{all_union(+Sets, ?SetUnion)}{all_union/2}{../bips/lib/fd_sets/all_union-2.html}]
         SetUnion is the union of all the sets in the list Sets 
\item[\biptxtref{all_intersection(+Sets, ?SetIntersection)}{all_intersection/2}{../bips/lib/fd_sets/all_intersection-2.html}]
         SetIntersection is the intersection of all the sets in the list Sets 
\end{description}


\subsection{Set Weights}

\begin{description}
\item[\biptxtref{weight(?Set, ++ElementWeights, ?Weight)}{weight/3}{../bips/lib/fd_sets/weight-3.html}]
         According to the array of element weights, the weight of set Set1 is Weight 
\end{description}


%----------------------------------------------------------------------
\section{Set Expressions}
%----------------------------------------------------------------------

In most positions where a set or set variable is expected one can also
use a set expression. A set expression is composed from ground sets
(integer lists), set variables, and the following set operators:
\begin{verbatim}
    Set1 /\ Set2       % intersection
    Set1 \/ Set2       % union
    Set1 \ Set2        % difference
\end{verbatim}
When such set expressions occur, they are translated into auxiliary
\bipref{intersection/3}{../bips/lib/fd_sets/intersection-3.html},
\bipref{union/3}{../bips/lib/fd_sets/union-3.html} and
\bipref{difference/3}{../bips/lib/fd_sets/difference-3.html}
constraints, respectively.


%----------------------------------------------------------------------
\section{Search Support}
%----------------------------------------------------------------------

The
\bipref{insetdomain/4}{../bips/lib/fd_sets/insetdomain-4.html}
predicate can be used to enumerate all ground instantiations of a set
variable, much like
\bipref{indomain/1}{../bips/lib/fd/indomain-1.html}
in the finite-domain case. 

\begin{description}
\item[\biptxtref{insetdomain(?Set, ?CardSel, ?ElemSel, ?Order)}{insetdomain/4}{../bips/lib/fd_sets/insetdomain-4.html}]
         Instantiate Set to a possible value 
\end{description}


%----------------------------------------------------------------------
\section{Example}
%----------------------------------------------------------------------

The following program computes so-called Steiner triplets.
These are triplets of numbers from 1 to N such that
any two triplets have at most one element in common.
\begin{verbatim}
:- lib(fd_sets).
:- lib(fd).

steiner(N, Sets) :-
        NB is N * (N-1) // 6,           % compute number of triplets
        intsets(Sets, NB, 1, N),        % initialise the set variables
        ( foreach(S,Sets) do
            #(S,3)                      % constrain their cardinality
        ),
        ( fromto(Sets,[S1|Ss],Ss,[]) do
            ( foreach(S2,Ss), param(S1) do
                #(S1 /\ S2, C),         % constrain the cardinality
                C #<= 1                 % of pairwise intersections
            )
        ),
        label_sets(Sets).               % search

label_sets([]).
label_sets([S|Ss]) :-
        insetdomain(S,_,_,_),
        label_sets(Ss).
\end{verbatim}
Here is an example of running this program
\begin{verbatim}
?- steiner(9,X).

X = [[1, 2, 3], [1, 4, 5], [1, 6, 7], [1, 8, 9],
     [2, 4, 6], [2, 5, 8], [2, 7, 9], [3, 4, 9],
     [3, 5, 7], [3, 6, 8], [4, 7, 8], [5, 6, 9]] More? (;)
\end{verbatim}

\index{library!fd_sets|)}

%HEVEA\cutend